﻿using System;
using System.Collections.Generic;



class MergeSort
{
    static List<int> mergeSort(List<int> MyList)
    {
        List<int> SortedList = new List<int>();
        if (MyList.Count <= 1)
        {
            return MyList;
        }
        List<int> LeftSide = new List<int>();
        List<int> RightSide = new List<int>();
        for (int i = 0; i < MyList.Count/2; i++)
			{
			    LeftSide.Add(MyList[i]);
			}
        for (int i = MyList.Count/2 ; i < MyList.Count; i++)
			{
			    RightSide.Add(MyList[i]);
			}
        LeftSide = mergeSort(LeftSide);
        RightSide = mergeSort(RightSide);
        SortedList = Merge(LeftSide, RightSide);
        return SortedList;

    }
    static List<int> Merge(List<int> First, List<int> Second)
    {
        int CountForFirstList = 0;
        int CountForSecondList = 0;
        List<int> FinalList = new List<int>();
        while (CountForFirstList != First.Count || Second.Count != CountForSecondList)
        {
            if (CountForFirstList != First.Count && Second.Count != CountForSecondList)
            {
                if (First[CountForFirstList] <= Second[CountForSecondList])
                {
                    FinalList.Add(First[CountForFirstList]);
                    CountForFirstList++;
                }
                else
                {
                    FinalList.Add(Second[CountForSecondList]);
                    CountForSecondList++;
                }
            }
            else if (CountForFirstList == First.Count)
            {
                while (Second.Count != CountForSecondList)
                {
                    FinalList.Add(Second[CountForSecondList]);
                    CountForSecondList++;
                }
            }
            else if (CountForSecondList == Second.Count)
            {
                while (First.Count != CountForFirstList)
                {
                    FinalList.Add(First[CountForFirstList]);
                    CountForFirstList++;
                }

            }
        }
        return FinalList;
        
    }
    static void Main()
    {
        List<int> MyList = new List<int>() { 4, 6, 11, -734, 33, -23, 654, 1, 123, 43, 786, 219409, 1114, 10 };
        List<int> SortedList = mergeSort(MyList);
        for (int i = 0; i < SortedList.Count; i++)
        {
            Console.Write(SortedList[i]+ " ");
        }
        Console.WriteLine();
        
    }
}
